package 树.BST;
/*
解题思路：
   这题不是普通的反序列化二叉树，而是要求你生成一颗二叉搜索树。

   抓住二叉搜索树这一点，我们可以直接取数组中间的值作为根节点，来构成一棵树---“一个节点该做的事”。然后剩下的交给递归框架
*/
public class 将有序数组转换为二叉搜索树_108 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private TreeNode dfs(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        // 以升序数组的中间元素作为根节点 root。
        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        // 递归的构建 root 的左子树与右子树。
        root.left = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi);
        return root;
    }
}
